package com.atguigu.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graphtest {
    
    private ArrayList<String> vertexList;
    private int[][] edges;
    private int numOfEdges;
    private boolean[] isVisited;

    public static void main(String[] args)
    {
        String Vertexs[] = {"A", "B", "C", "D"};

        Graphtest graph = new Graphtest(4);
		
		for(String vertex: Vertexs) {
			graph.add(vertex);
		}

        graph.insertEdge(0, 1);
		graph.insertEdge(0, 2);
        graph.insertEdge(1, 0);
		graph.insertEdge(1, 3);
        // graph.insertEdge(1, 2);
        // graph.insertEdge(2, 3);
        // graph.insertEdge(2, 0);
		// graph.insertEdge(1, 4);
		// graph.insertEdge(3, 7);
		// graph.insertEdge(4, 7);
		// graph.insertEdge(2, 5);
		// graph.insertEdge(2, 6);
		// graph.insertEdge(5, 6);
        graph.dfs();

        graph.showGraph();
    }

    public Graphtest(int n){
        vertexList =new ArrayList<>();
        edges=new int[n][n];
        numOfEdges=0;
        isVisited = new boolean[n];

   }

   // 新增节点
   public void add(String node)
   {
       vertexList.add(node);
   }

   // 新增边
   public void insertEdge(int n,int v)
   {
      edges[n][v]=1;
      edges[v][n]=1;
   }


   public void showGraph()
   {
       for(int[] link:edges)
       {
           System.out.println(Arrays.toString(link));
       }
   }

   // 发现第一个邻接节点
   public int getFirstNode(int v)
   {
       for(int i=0;i<vertexList.size();i++)
       {
           if(edges[v][i]==1)
           {
               return i;
           }
       }
       return -1;
   }


   // 按行搜索
   public int getNextNode(int v,int n)
   {
       for(int j=n+1;j<vertexList.size();j++)
       {
           if(edges[v][j]==1)
           {
               return j;
           }
       }
       return -1;
   }

   public String getValueByIndex(int index)
   {
       return vertexList.get(index);
   }

   // 深度遍历

   public void dfs()
   {
    dfs(isVisited,0);
    //    for(int i=0;i<vertexList.size();i++)
    //    {
    //        if(!isVisited[i])
    //        {
    //        dfs(isVisited,i);
    //        }
    //    }
   }

   public void dfs(boolean[] isVisited,int index)
   {
      System.out.print(getValueByIndex(index) + "->");
       isVisited[index]= true;
       int first = getFirstNode(index);
       // 如果没有被访问
       while(first>-1)
       {
           // 如果没有被访问就
           if(!isVisited[first])
           {
            dfs(isVisited,first);
           }
           first=getNextNode(index, first);
       }
   }

   // 广度优先遍历,需要借助队列的作用

   public void bfs(boolean[] isVisited,int index)
   {
       System.out.print(getValueByIndex(index) + "->");
       int u;
       int v;
       
    //    QueueL
    //    isVisited[index]=true;
       int first = getFirstNode(index);

       while(!isVisited[first])
       {
          
           u = getNextNode(index,first);
       }
   }

   

}